package com.zyong.heap;

import java.math.BigInteger;
import java.util.Arrays;

public class CreateBFromATencent {

    /**
     * 题目：输入一个数组A[1,2,...n]，求输入B，使得数组B中的第i个数字B[i]=A[0]*A[1]*...*A[i-1]*A[i+1]*...*A[N-1].
     * 要求
     * 1.不得使用除法
     * 2.不得新建变量--how?
     * see http://weibo.com/zhedahht
     */
    public static void main(String[] args) {
        int size =3;
        int[] a=new int[size];
        for(int i=0;i<size;i++){
            a[i]=i+1;
        }
        
        System.out.println(Arrays.toString(a));
        BigInteger[] b1=create(a);//I don't like 'BigInteger',but program will overflow without using it.
        System.out.println(Arrays.toString(b1));
        
        BigInteger[] b2=createWithoutDivision(a);
        System.out.println(Arrays.toString(b2));
    }

    //general solution.Use division
    public static BigInteger[] create(int[] a){
        if(a==null||a.length==0){
            return new BigInteger[0];
        }
        int len=a.length;
        BigInteger[] b=new BigInteger[len];
        //BigInteger product=new BigInteger("1");
        BigInteger product=BigInteger.valueOf(1);//<Effective Java>.Use "static factory method" instead of constructor sometimes. 
        BigInteger[] aa=new BigInteger[len];
        for(int i=0;i<len;i++){
            aa[i]=BigInteger.valueOf(a[i]);
            product=product.multiply(aa[i]);
        }
        for(int i=0;i<len;i++){
            b[i]=product.divide(aa[i]);
        }
        return b;
    }
    
    //not use division.
    public static BigInteger[] createWithoutDivision(int[] a){
        if(a==null||a.length==0){
            return new BigInteger[0];
        }
        int len=a.length;
        BigInteger[] b=new BigInteger[len];
        BigInteger[] aa=new BigInteger[len];
        b[0]=BigInteger.valueOf(1);
        for(int i=0;i<len;i++){
            aa[i]=BigInteger.valueOf(a[i]);
            if(i+1<len){
                b[i+1]=b[i].multiply(aa[i]);
            }
        }
        BigInteger tmp=BigInteger.valueOf(1);
        for(int i=len-2;i>=0;i--){
            tmp=tmp.multiply(aa[i+1]);
            b[i]=b[i].multiply(tmp);
        }
        return b;
    }
}



